/*
*author: Yixin Luo
*date:14/6/21
*function:线性表数据结构的实现，数据结构学习
*/
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100//初始的线性表大小
#define LIST_INC       10//每次加的大小
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int ElemType;// 数据表的类型
typedef struct{
     ElemType * elem;//起始的数据地址
     int        length;//当前长度
     int        listsize;//当前分配的空间的长度
}SqList;
int InitList_Sq(SqList* L)//初始化线性表，分配空间
{
    (*L).elem=(ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!(*L).elem) exit(OVERFLOW);
    (*L).length=0;
    (*L).listsize=LIST_INIT_SIZE;
    return OK;
}
void show(SqList L)//打印线性表中的所有元素
{   
    int i;
    for(i=0;i<L.length;i++)
    {
       printf("the %d is %d\n",i,L.elem[i]);
    }
}
int ListAdd_Sq(SqList* L,ElemType e)//在线性表的最后加上一个数据
{   
    if((*L).length>=(*L).listsize)
    {   ElemType * newbase;
        newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LIST_INC)*sizeof(ElemType));
        if(!newbase) exit(OVERFLOW);
        (*L).listsize+=LIST_INC;
        (*L).elem=newbase;
    }
    (*L).elem[(*L).length]=e;
    (*L).length++;
    return OK;
}
int ListInsert_Sq(SqList* L,int i,ElemType e)//在指定位置i插入e
{   
    if(i<=0||i>(*L).length)
    {
      printf("the num is wrong\n");
      return ERROR;
    }
     if((*L).length>=(*L).listsize)
    {   ElemType * newbase;
        newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LIST_INC)*sizeof(ElemType));
        if(!newbase) exit(OVERFLOW);
        (*L).listsize+=LIST_INC;
        (*L).elem=newbase;
    }
    ElemType* q;
    q=&((*L).elem[i-1]);
    ElemType* p;
    for(p=&((*L).elem[((*L).length-1)]);p>=q;p--) *(p+1)=*p;
    *q=e;
    (*L).length++;
    return OK;
}
int ListDelete_Sq(SqList* L,int i)//在指定位置删除数据
{  
    if(i<=0||i>(*L).length)
    {
      printf("the num is wrong\n");
      return ERROR;
    }
   ElemType* q;
   q=&((*L).elem[i-1]);
   ElemType* p;
   p=&((*L).elem[(*L).length-1]);
   for(;q<p;q++) *q=*(q+1);
   (*L).length--;
   return OK;
}
void SortList_Sq(SqList* L)//从小到大排序
{
   ElemType e;
   int i;
   int j;
   for(i=0;i<(*L).length;i++)
   {
      for(j=i+1;j<(*L).length;j++)
      {
          if((*L).elem[i]>(*L).elem[j])
          {
              e=(*L).elem[i];
              (*L).elem[i]=(*L).elem[j];
              (*L).elem[j]=e;
          }
      }
   }
}
void MergeList_Sq(SqList la,SqList lb,SqList* lsum)//将线性表la与lb合并
{
    SortList_Sq(&la);
    SortList_Sq(&lb);
    ElemType* pa=la.elem;
    ElemType* pb=lb.elem;
    ElemType* pc=(*lsum).elem;
    (*lsum).length=la.length+lb.length;
    ElemType * newbase;
    newbase=(ElemType *) realloc((*lsum).elem,(*lsum).length*sizeof(ElemType));  
    if(!newbase) exit(OVERFLOW);
    while(pa<=&pa[la.length-1]&&pb<=&pb[lb.length-1]){
    if(*pa>*pb)
    {
       ListAdd_Sq(&lsum,*pb);
    }
    else
       ListAdd_Sq(&lsum,*pa);
    }
    while(pa<=&pa[la.length-1])  *pc++=*pa++;
    while(pa<=&pa[la.length-1])  *pc++=*pb++;
}
int main(void)//主函数
{
    SqList sl,sl2;
    InitList_Sq(&sl);
    ListAdd_Sq(&sl,1);
    ListAdd_Sq(&sl,2);
    ListInsert_Sq(&sl,2,3);
    ListInsert_Sq(&sl,2,4);
     InitList_Sq(&sl2);
    ListAdd_Sq(&sl2,1);
    ListAdd_Sq(&sl2,2);
    ListInsert_Sq(&sl2,2,3);
    ListInsert_Sq(&sl2,2,4);
    MergeList_Sq(sl,sl2,&sl);
    show(sl);
}







